package com.agile.leetcode.regix;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

/**
 * 有一个同学在学习分式。他需要将一个连分数化成最简分数，你能帮助他吗？
 *
 * 连分数是形如上图的分式。在本题中，所有系数都是大于等于0的整数。
 *  a0+1/(a1+1/(a2+1)+1/(a3+1)..)
 *
 * 输入的cont代表连分数的系数（cont[0]代表上图的a0，以此类推）。返回一个长度为2的数组[n, m]，使得连分数的值等于n / m，且n, m最大公约数为1。
 * 输入：cont = [3, 2, 0, 2]
 * 输出：[13, 4]
 * 解释：原连分数等价于3 + (1 / (2 + (1 / (0 + 1 / 2))))。注意[26, 8], [-13, -4]都不是正确答案。
 *
 * 输入：cont = [0, 0, 3]
 * 输出：[3, 1]
 * 解释：如果答案是整数，令分母为1即可。
 * @Author ChenZhangKun
 * @Date 2020/7/8 13:30
 */
public class FractionalReduction {
    public static void main(String[] args) {
        int[] array={0,0,3};
        FractionalReduction fractionalReduction = new FractionalReduction();
        String string = fractionalReduction.traverseToString(array);
        System.out.println(string);
        List<String> list = fractionalReduction.toInfixExpression(string);
       // System.out.println(fractionalReduction.getResult(fractionalReduction.infixToSuffixExpression(list)));

        int[] fraction = fractionalReduction.fraction(array);
        System.out.println(Arrays.toString(fraction));

    }
    // 解法,通分
    public int[] fraction(int[] cont) {
        int[] res = new int[2];
        res[0] = cont[cont.length - 1];
        res[1] = 1;
        for (int i = cont.length - 1; i > 0; i--) {
            int temp = res[0];
            // 循环次数为通分次数，可以依据通分的步骤俩推理
            res[0] = cont[i - 1] * res[0] + res[1];
            res[1] = temp;// 交换分子分母
        }
        return res;
    }




    private String traverseToString(int[] array){
        String str="";
        for (int i = 0; i < array.length; i++) {
            if (i!=array.length-1){
                if (i==0){
                    str+=array[i];
                }else {
                    str+="+(1/("+array[i];
                }
            }else {
                str+="+1/"+array[i];
                for (int j = 0; j < array.length; j++) {
                    str+=")";
                }

            }
        }
        return str;
    }
    /**
     * 后缀表达式计算结果
     * @param list
     * @return
     */
    private  int getResult(List<String> list){
        // 创建栈
        Stack<String> stack=new Stack<>();
        // 遍历list
        for (String s : list) {
            // 使用正则表达式来取出数字
            if (s.matches("\\d+")){
                // 入栈
                stack.push(s);
            }else {
                // 弹出两个数运算后再入栈
                int num2 =Integer.parseInt( stack.pop());
                int num1 = Integer.parseInt(stack.pop());
                int res=0;
                // 判断该符号是什么
                if (s.equals("+")){
                    res= num1+num2;
                }else if (s.equals("-")){
                    res=num1-num2;
                }else if (s.equals("*")){
                    res=num1*num2;
                }else {
                    res=num1/num2;
                }
                // 计算结果从新压入栈中
                stack.push(res+"");
            }
        }
        // 得到计算的结果
        return Integer.parseInt(stack.pop());
    }

    /**
     * 将中缀表达式字符串加入集合中，得到集合的中缀表达式
     * @param inFixExpression 传入种植表达式
     * @return
     */
    // 将表达式转为list集合存储
    public  List<String> toInfixExpression(String inFixExpression){
        List<String> list=new ArrayList<>(15);
        // 指针，用于遍历
        int index=0;
        // 对多位数的拼接工作
        String s;
        // 遍历到的字符是否是符号
        char ch=' ';
        do {
            if ((ch=inFixExpression.charAt(index))>57||(ch=inFixExpression.charAt(index))<48){
                // 非数字
                list.add(""+ch);
                index++;
            }else {
                s="";
                // 判断数字到那一位结束
                while (index<inFixExpression.length()&&(ch=inFixExpression.charAt(index))>=48&&(ch=inFixExpression.charAt(index))<=57){
                    s+=ch;
                    index++;
                }
                // 将数字加入集合中
                list.add(s);
            }
        }while (index<inFixExpression.length());
        return list;
    }

    /**
     * 中缀表达式的集合转换为后缀表达式
     * @param list 中缀表达式的list集合
     * @return
     */
    public  List<String> infixToSuffixExpression(List<String> list){
        // 定义符号栈
        Stack<String> s1=new Stack<>();
        // 定义数字栈 因为数字栈没有弹栈操作，可以用list代替
        //Stack<String> s2=new Stack<>();
        List<String> numList=new ArrayList<>(15);
        // 遍历集合
        for (String s : list) {
            // 是数字的情况
            if (s.matches("\\d+")){
                numList.add(s);
            }else if (s.equals("(")){
                // 左括号进入符号栈
                s1.push(s);
            }else if (s.equals(")")){
                // 右括号的的情况
                // 将符号栈中的左括号前的符号加入数字栈
                while (!s1.peek().equals("(")){
                    numList.add(s1.pop());
                }
                // 将小括号弹出站顶
                s1.pop();
            }else {
                // 优先级的问题
                // s1为空时或栈顶为左括号时，直接加入符号栈
                if (s1.isEmpty()||s1.peek().equals("(")){
                    s1.push(s);
                }else  {
                    // s1栈顶的运算符的优先级比当前运算符的优先级大的时候
                    while (s1.size() != 0 && Operation.getPriority(s1.peek()) >= Operation.getPriority(s)) {
                        // 将栈顶元素压如数字栈中
                        numList.add(s1.pop());
                    }
                    // 优先级大于栈顶操作符的优先级时当前操作符压入栈顶
                    s1.push(s);
                }
            }
        }
        // 将s1中的符号加入数字栈中
        while (true){
            if (s1.size()!=0){
                numList.add(s1.pop());
            }else {
                break;
            }
        }
        return numList;
    }

}
/**
 * 获取运算符的优先级
 */
class Operation{
    private static int ADD=1;
    private static int SUB=1;
    private static int MUL=2;
    private static int DIV=2;
    // 返回优先级
    public static int getPriority(String operation){
        int result=0;
        switch (operation){
            case "+":
                result=ADD;
                break;
            case "-":
                result= SUB;
                break;
            case "*":
                result=MUL;
                break;
            case "/":
                result=DIV;
                break;
        }
        return result;
    }
}

